package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

/**
 * 判断是否是搜索二叉树，中序遍历判断是不是递增，这里使用 morris进行中序遍历，时间复杂度为O(n),空间为O(1)
 */
public class _14_判断二叉树是否为搜索二叉树_morris {


    public static boolean isSearchBinaryTree(TreeNode root) {

        int beforeVal = Integer.MIN_VALUE;

        TreeNode node = root;

        while (node != null) {

            TreeNode preNode = node.left;

            if (preNode != null) {

                while (preNode.right != null && preNode.right != node) {

                    preNode = preNode.right;
                }

                if (preNode.right == null) {

                    preNode.right = node;
                    node = node.left;
                }

                if (preNode.right == node){

                    if (node.val < beforeVal) {

                        return false;
                    }
                    beforeVal = node.val;
                    node = node.right;
                    preNode.right = null;
                }

            }else {

                if (node.val < beforeVal) {

                    return false;
                }
                beforeVal = node.val;
                // 在前面已经为 node.right 赋值为中序遍历的下一个元素
                node = node.right;
            }
        }


        return true;
    }


    public static void main(String[] args) {

        /**
         *                  6
         *
         *               3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(9);
        t1.right.right = new TreeNode(10);

        System.out.println(isSearchBinaryTree(t1));

    }
}
